1. Field of the Invention
The invention relates to a method for performing scheduling, routing and access control in a computer network and, more specifically, a method for performing scheduling, routing and access control in an ad hoc wireless network.
2. Description of the Related Art
Computer networks based upon a series of nodes and servers interconnected by physical wiring have been well known for some time (e.g., an Ethernet or a Token-ring network). With the rapid development of the Internet, these computer networks must not only communicate effectively within their own domain or environment, but also must communicate between networks of different types.
An example of a prior art physical wire-based wide-area network 10 is shown in FIG. 1 comprising a first local area network 12 having several nodes 14 interconnected by a wire-based network 16. A network sever 18 located on the first local area network 12 is interconnected to a Central Telephone Office (CTO) box 20 for interconnection of the local area network 12 to a Public Switched Telephone Network (PSTN), or a world wide network more commonly known as the Internet 22. A second local area network 24 is also interconnected to the Internet 22, via a web server 26 through a second CTO box 28. The second local area network 24 also can have several nodes 30 thereon.
A reference model for Open Systems Interconnection (OSI) has been defined by the International Standardization Organization (ISO) to put names to the different tasks a computer network has to fulfill to order to perform these inter-network types of communications. An example of such an inter-network communication is shown by a dashed arrow “A” in FIG. 1 for communication between a node 14 on the first local area network 12 and a node 30 on the second local area network 24.
The ISO model defines seven layers, providing a logical grouping of the network functions. This model is good for teaching, and for planning the implementation of a computer network. Furthermore, dividing functionality in defined layers has the advantage that different parts of the network can be provided from different vendors and still work together.
As schematically illustrated in FIG. 2 and described in greater detail below, the OST network protocol 40 has seven generally independent layers: the physical layer 42, the link layer 44, the network layer 46, the transport layer 48, the session layer 50, the presentation layer 52 and the application layer 54.
The physical layer 42 is responsible for converting the stream of digital bits from the layers above to a physical stream capable of being transported between two nodes on whatever physical medium happens to comprise the network (e.g., wires, cables, radio, light, etc.). The link layer 44 is responsible for carrying packets across a link (i.e., a network interconnection) between two nodes and making sure that the packets are not damaged, and that they arrive in the correct order. The network layer 46 transmits those packets from one node to another across the network, and the organization of such a network, possibly consisting of several independent physical networks typically via a global unique address structure.
The transport layer 48 transports data from one program to another across a network and typically also always includes another level of addressing (e.g., network sockets). While Quality of Service (QoS) is often defined at this layer, the broader definition of QoS includes metrics such as delay and bit loss or packet loss at the previous three layers (physical, link and network). The remaining three layers 50-54 (i.e., session layer 50, presentation layer 52 and application layer 54) are of less relevance when addressing networking concerns since these three layers 50-54 essentially relate to how a particular node on a network processes data received by the four underlying layers 42-48 (i.e., physical layer 42, link layer 44, network layer 46 and transport layer 48).
The conventional wisdom in transmitting packets of data across networks was to essentially isolate each of the layers 42-54 of the OSI protocol 40. For example, information/data generated by a node for transmission to another node via the session, presentation and application layers 50-54 are passed into a “virtual pipe” between a pair of nodes (such as a client and a server in a conventional wire-based network) created by the transport layer 48. The data are then handed off to the network layer 46 which decides the route the data will take to their specified destination, i.e., the network layer performs the “routing” function of getting data from one node to another. The link layer 44 then takes over and determines how much available capacity on the network a particular node will be granted for transmissions and how this capacity is distributed among multiple data flows at the emanating or terminating at the node, handles error checking on the transmission and receipt of the data packets and arbitrates between multiple nodes attempting to transmit packets. These functions, typically performed by the link layer 44, are referred to commonly as “scheduling”, i.e., which flow within which node gets to transmit, at what time and for how long, and “access control”, i.e., when new nodes are granted rights to transmit or allowed to request bandwidth.
Quality of Service (or QoS) is generally measured to determine whether these scheduling, routing and access control functions are being performed adequately by a network. Two performance metrics, i.e., throughput and delay, are typically measured to provide specific criteria as to the QoS provided by the network. Throughput measures the “effective traffic” on the network, generally in the number of bits transmitted over the network over time between a pair of points on the network. Delay measures the time it takes to transmit the data between these two points. In this application, the indicator Xn is used to indicate the throughput rate (typically in bits/sec) of a particular network at node n and the indicator δn is used to indicate the delay in seconds in packet transmission. Obviously, for a network to be effective, its routing, scheduling and access control algorithms should be designed to maximize throughput (Xn) and minimize delay (δn) for each node on the network.
Thus, with the conventional wisdom outlined above, the routing decisions made at the network layer 46 were made independent of the access control and scheduling protocols made at the link layer 44. In addition, virtually no consideration was made in the conventional wisdom of computer networking with regard to the physical layer 42 (as described in the OSI protocol 40) because of the high capacities and reliabilities of the media used in typical wire-based networks such as that shown in FIG. 1.
This type of designed independence between the network layer 46, the link layer 44 and the physical layer 42 has some drawbacks even in the generally reliable wire-based networking environment. For example, because node-to-node routing decisions of the network layer 46 are made independent of capacity assignments of the access control and scheduling protocols of the link layer 44, data on the network may be routed through busy nodes on the network (i.e., the node though which data is routed does not have the capacity to handle the data packet) and new high-capacity, free nodes on the network may not be considered by the routing decisions of the network layer 46. In both of these situations, throughput (Xn) would decrease and delay (δn) would increase. The converse of this drawback is also true in that access control and scheduling decisions made at the link layer 44 are made unaware (i.e., independent) of variations in link load (i.e., a particular path between a pair of nodes) resulting from route assignments made at the network layer 46. In either case, QoS is certainly adversely affected.
Further, changes in the network topology and the ability of particular links between nodes to transmit data (i.e., link quality) affect the capacity of a particular link to transmit data effectively. Independent decisions made in routing and access control algorithms would not account for this situation as well.
These problems are exacerbated when the network includes wireless elements, and especially in an ad hoc wireless network, shown by example in FIG. 3 wherein an ad hoc wireless network 60 comprises several disparate nodes 62 interconnected by wireless links 64. It will be understood that the nodes 62 in an ad hoc wireless network 60 are typically formed into a clique, shown by phantom outline 66 in FIG. 3 wherein a subset of nodes on the network 60 can each communicate with every other node in the clique 66, or a cluster, shown by phantom outline 68 in FIG. 3 wherein at least one node 62 in a subset of nodes on the network 60 can communicate with every other node in the cluster 68.
In the wireless network 60, the predefined “links” between nodes on the network are less defined than with physical high-capacity, low-error rate wires as in the network 10 shown in FIG. 1. In a wireless network 60, the links 64 are aware of one another by cliquing or clustering algorithms which form the often transient cliques 66 and clusters 68 on the wireless network 60.
However, the great benefits of wireless networks 60, in that nodes 62 can be easily “dropped” into place and immediately formed into a wireless network and that they can be immediately and dynamically reconfigured in location, also provide the greatest difficulties for performing scheduling, routing and access control on them. In addition to the drawbacks of independently making the scheduling, routing and access control decisions as indicated by the convention wisdom of the OSI protocol 40 as outlined above, several additional problems surface when these independent scheduling, routing and access control decisions are made in a wireless environment.
For example, in addition to nodes 62 being moveable on the network 60, nodes 62 can be added or deleted to and from the network 60 without notice to the other nodes and the scheduling, routing and access control decisions of prior art systems cannot adapt. The network layer 46 in prior art wireless systems cannot make effective routing decisions because the nodes 62 can change often in presence and location. The link layer 44 cannot adapt to changing topology since convention access control and scheduling decisions are generally made on a presumed topology for the network. Finally, since the physical layer 42 is generally presumed to be a high-capacity medium in prior art networking environments, changes in the bandwidth or even elimination of bandwidth on particular nodes 62 or links 64 of a wireless network 60 cause independently-made scheduling, routing and access control decisions to fail in the unpredictable medium of a wireless environment (i.e., unpredictable and highly variable in errors and capacity).
In summary, the prior art wire-based and wireless networking schemes that make independent scheduling, routing and access control decisions in the corresponding physical layer 42, link layer 44 and network layer 46 are unable to adapt efficiently to an ad hoc wireless network environment. The prior art cannot adapt adequately to the dynamic reconfiguration of an ad hoc wireless network and it cannot account for the wide variations of the physical medium, namely a wireless channel.